//给定一个字符串，请将字符串里的字符按照出现的频率降序排列。 
//
// 示例 1: 
//
// 
//输入:
//"tree"
//
//输出:
//"eert"
//
//解释:
//'e'出现两次，'r'和't'都只出现一次。
//因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
// 
//
// 示例 2: 
//
// 
//输入:
//"cccaaa"
//
//输出:
//"cccaaa"
//
//解释:
//'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
//注意"cacaca"是不正确的，因为相同的字母必须放在一起。
// 
//
// 示例 3: 
//
// 
//输入:
//"Aabb"
//
//输出:
//"bbAa"
//
//解释:
//此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
//注意'A'和'a'被认为是两种不同的字符。
// 
// Related Topics 哈希表 字符串 桶排序 计数 排序 堆（优先队列） 
// 👍 348 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class SortCharactersByFrequency {
    public static void main(String[] args) {
        new SortCharactersByFrequency().new Solution().frequencySort2("tree");

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 使用HashMap来统计元素出现的次数
         * 构建大顶堆，然后顺序输出？
         * 离谱，这种方法还真行，我是构建了一个大顶堆，在堆中放的key，比较器比较的是对应的value
         * 确实是这种思路，也可以使用数组（桶排序）来代替hashmap和堆的作用
         *
         */
        public String frequencySort(String s) {
            Map<Character,Integer> map = new HashMap<>();
            char[] chars = s.toCharArray();
            for (char c : chars) map.put(c, map.getOrDefault(c, 0)+1);
            //这里重写了构造器，构建大顶堆
            PriorityQueue<Character> pq = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
            for (Character c : map.keySet()) pq.add(c);
            StringBuffer stringBuffer = new StringBuffer();
            while (!pq.isEmpty()){
                //获取并删除出现次数最多的字符
                Character c = pq.poll();
                Integer times = map.get(c);
                char[] temp = new char[times];
                Arrays.fill(temp, c);
                //拼接字符串
                stringBuffer.append(temp);
            }
            return stringBuffer.toString();
        }

        /**
         * 使用二维数组进行存储以及排序
         */
        public String frequencySort2(String s) {
            //创建二维数组，包含所有字母字符的二维数组 0代表字符，1代表次数
            int[][] cnts = new int[128][2];
            for (int i = 0; i < 128 ; i++) cnts[i][0] = i;//为所有字符赋初值
            for (char c : s.toCharArray()) cnts[c][1]++;//根据字符统计出现次数
            Arrays.sort(cnts, (a, b)->{//重写排序比较器
                if (a[1] != b[1]) return b[1] - a[1];//优先按照出现次数进行排序
                return a[0] - b[0];//出现次数相同就按照字母顺序进行排序
            });
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 128; i++) {//拼接字符串
                char c = (char)cnts[i][0];
                int k = cnts[i][1];
                if (k==0) break;
                while (k-- > 0) sb.append(c);
            }
            return sb.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}